import java.util.*;

public class Main {
    public static void main(String[] args) {
        System.out.println("Hello world!");
    }
}

class Solution {
    public int ladderLength(String beginWord, String endWord, List<String> wordList) {
        if(beginWord.equals(endWord)) return 0;
        Set<String> visited = new HashSet<>();//标记该序列是否转换过
        Set<String> words = new HashSet<>();//存储字典所有单词
        words.addAll(wordList);
        if (!words.contains(endWord)) return 0;

        Queue<String> queue = new LinkedList<>();
        queue.add(beginWord);
        visited.add(beginWord);
        int steps = 1;
        int n = beginWord.length();
        while(!queue.isEmpty()){
            int sz = queue.size();
            steps++;
            for (int i = 0; i < sz; i++) {
                String poll = queue.poll();
                for(int j = 0; j < n; j++){
                    char[] tmp = poll.toCharArray();
                    for(char ch = 'a'; ch <= 'z'; ch++){
                        tmp[j] = ch;
                        String s = new String(tmp);
                        if(!visited.contains(s) && words.contains(s)){
                            if(s.equals(endWord)) return steps;
                            queue.add(s);
                            visited.add(s);
                        }
                    }
                }
            }
        }

        return 0;
    }
}